package com.c2b.algorithm.leetcode.base;

import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150">有效的括号(Valid Parentheses)</a>
 * <p>给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。</p>
 * <p>
 * 有效字符串需满足：
 *     <ul>
 *         <li>左括号必须用相同类型的右括号闭合。</li>
 *         <li>左括号必须以正确的顺序闭合</li>
 *         <li>每个右括号都有一个对应的相同类型的左括号</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "()"
 *      输出：true
 *
 * 示例 2：
 *      输入：s = "()[]{}"
 *      输出：true
 *
 * 示例 3：
 *      输入：s = "(]"
 *      输出：false
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= s.length <= 10^4</li>
 *         <li>s 仅由括号 '()[]{}' 组成</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/11 17:16
 */
public class LC0020ValidParentheses_S {

    static class Solution {
        public boolean isValid(String s) {
            // 特殊校验：如果括号的数量为奇数个，一定无效
            if (s.length() % 2 == 1) {
                return false;
            }
            Stack<Character> characterStack = new Stack<>();
            for (char ch : s.toCharArray()) {
                // 如果是左括号，直接入栈
                if (ch == '(' || ch == '[' || ch == '{') {
                    characterStack.push(ch);
                } else {
                    // 如果是右括号
                    // 需要先判断栈是否为空，如果为空，则为false；否则需要判断栈顶的括号与当前右括号是否匹配
                    if (ch == ')') {
                        if (characterStack.isEmpty() || characterStack.pop() != '(') {
                            return false;
                        }
                    } else if (ch == ']') {
                        if (characterStack.isEmpty() || characterStack.pop() != '[') {
                            return false;
                        }
                    } else if (ch == '}') {
                        if (characterStack.isEmpty() || characterStack.pop() != '{') {
                            return false;
                        }
                    }  // ignored
                }
            }
            return characterStack.isEmpty();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValid("()"));
        System.out.println(solution.isValid("()[]{}"));
        System.out.println(solution.isValid("(]"));
    }
}
